home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / MPW_TOOL / TOOLS / TOOLS_WI / FAST_LEX / ECS.C < prev    next >
Text File  |  1988-07-04  |  5KB  |  219 lines
  1. /* ecs - equivalence class routines */
  2.  
  3. /*
  4.  * Copyright (c) 1987, the University of California
  5.  * 
  6.  * The United States Government has rights in this work pursuant to
  7.  * contract no. DE-AC03-76SF00098 between the United States Department of
  8.  * Energy and the University of California.
  9.  * 
  10.  * This program may be redistributed.  Enhancements and derivative works
  11.  * may be created provided the new works, if made available to the general
  12.  * public, are made available for use by anyone.
  13.  */
  14.  
  15. #include "flexdef.h"
  16.  
  17. /* ccl2ecl - convert character classes to set of equivalence classes
  18.  *
  19.  * synopsis
  20.  *    ccl2ecl();
  21.  */
  22.  
  23. ccl2ecl()
  24.  
  25.     {
  26.     int i, ich, newlen, cclp, ccls, cclmec;
  27.  
  28.     for ( i = 1; i <= lastccl; ++i )
  29.     {
  30.     /* we loop through each character class, and for each character
  31.      * in the class, add the character's equivalence class to the
  32.      * new "character" class we are creating.  Thus when we are all
  33.      * done, character classes will really consist of collections
  34.      * of equivalence classes
  35.      */
  36.  
  37.     newlen = 0;
  38.     cclp = cclmap[i];
  39.  
  40.     for ( ccls = 0; ccls < ccllen[i]; ++ccls )
  41.         {
  42.         ich = ccltbl[cclp + ccls] & BYTEMASK;
  43.         cclmec = ecgroup[ich];
  44.         if ( cclmec > 0 )
  45.         {
  46.         ccltbl[cclp + newlen] = cclmec;
  47.         ++newlen;
  48.         }
  49.         }
  50.  
  51.     ccllen[i] = newlen;
  52.     }
  53.     }
  54.  
  55.  
  56. /* cre8ecs - associate equivalence class numbers with class members
  57.  *
  58.  * synopsis
  59.  *    int cre8ecs();
  60.  *    number of classes = cre8ecs( fwd, bck, num );
  61.  *
  62.  *  fwd is the forward linked-list of equivalence class members.  bck
  63.  *  is the backward linked-list, and num is the number of class members.
  64.  *  Returned is the number of classes.
  65.  */
  66.  
  67. int cre8ecs( fwd, bck, num )
  68. int fwd[], bck[], num;
  69.  
  70.     {
  71.     int i, j, numcl;
  72.  
  73.     numcl = 0;
  74.  
  75.     /* create equivalence class numbers.  From now on, abs( bck(x) )
  76.      * is the equivalence class number for object x.  If bck(x)
  77.      * is positive, then x is the representative of its equivalence
  78.      * class.
  79.      */
  80.  
  81.     for ( i = 1; i <= num; ++i )
  82.     if ( bck[i] == NIL )
  83.         {
  84.         bck[i] = ++numcl;
  85.         for ( j = fwd[i]; j != NIL; j = fwd[j] )
  86.         bck[j] = -numcl;
  87.         }
  88.  
  89.     return ( numcl );
  90.     }
  91.  
  92.  
  93. /* mkeccl - update equivalence classes based on character class xtions
  94.  *
  95.  * synopsis
  96.  *    char ccls[];
  97.  *    int lenccl, fwd[llsiz], bck[llsiz], llsiz;
  98.  *    mkeccl( ccls, lenccl, fwd, bck, llsiz );
  99.  *
  100.  * where ccls contains the elements of the character class, lenccl is the
  101.  * number of elements in the ccl, fwd is the forward link-list of equivalent
  102.  * characters, bck is the backward link-list, and llsiz size of the link-list
  103.  *
  104.  * Modified by Earle R. Horton, May, 1988 to allow for the possibility that
  105.  * negative characters may be valid in the character set of the compiler.
  106.  */
  107.  
  108. mkeccl( ccls, lenccl, fwd, bck, llsiz )
  109. char ccls[];
  110. int lenccl, fwd[], bck[], llsiz;
  111.  
  112.     {
  113.     int cclp, oldec, newec;
  114.     int cclm, i, j;
  115.     short *tmpccl;
  116.     
  117.     /* [ERH] Read chars into a short array on the stack. */
  118.     tmpccl = (short *)alloca(current_max_ccl_tbl_size * sizeof(short));
  119.     for (i=0; i < current_max_ccl_tbl_size; i++)
  120.         tmpccl[i] = ccls[i] & BYTEMASK;
  121.  
  122.     /* note that it doesn't matter whether or not the character class is
  123.      * negated.  The same results will be obtained in either case.
  124.      */
  125.  
  126.     cclp = 0;
  127.  
  128.     while ( cclp < lenccl )
  129.     {
  130.     cclm = tmpccl[cclp];
  131.     oldec = bck[cclm];
  132.     newec = cclm;
  133.  
  134.     j = cclp + 1;
  135.  
  136.     for ( i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i] )
  137.         { /* look for the symbol in the character class */
  138.         for ( ; j < lenccl && tmpccl[j] <= i; ++j )
  139.         if ( tmpccl[j] == i )
  140.             {
  141.             /* we found an old companion of cclm in the ccl.
  142.              * link it into the new equivalence class and flag it as
  143.              * having been processed
  144.              */
  145.  
  146.             bck[i] = newec;
  147.             fwd[newec] = i;
  148.             newec = i;
  149.             tmpccl[j] = -i;    /* set flag so we don't reprocess */
  150.             /*
  151.              * [ERH]  This trick will not work if negative characters are
  152.              * valid.  E.g. DEC multi-nationals, Macintosh option-characters.
  153.              */
  154.  
  155.             /* get next equivalence class member */
  156.             /* next 2 */ goto next_pt;
  157.             }
  158.  
  159.         /* symbol isn't in character class.  Put it in the old equivalence
  160.          * class
  161.          */
  162.  
  163.         bck[i] = oldec;
  164.  
  165.         if ( oldec != NIL )
  166.         fwd[oldec] = i;
  167.  
  168.         oldec = i;
  169. next_pt:
  170.         ;
  171.         }
  172.  
  173.     if ( bck[cclm] != NIL || oldec != bck[cclm] )
  174.         {
  175.         bck[cclm] = NIL;
  176.         fwd[oldec] = NIL;
  177.         }
  178.  
  179.     fwd[newec] = NIL;
  180.  
  181.     /* find next ccl member to process */
  182.  
  183.     for ( ++cclp; tmpccl[cclp] < 0 && cclp < lenccl; ++cclp )
  184.         {
  185.         /* reset "doesn't need processing" flag */
  186.         tmpccl[cclp] = -tmpccl[cclp];
  187.         }
  188.     }
  189.     /* [ERH] Feed shorts back into chars. */
  190.     for (i=0; i < current_max_ccl_tbl_size; i++)
  191.         ccls[i] = tmpccl[i];
  192.     }
  193.  
  194.  
  195. /* mkechar - create equivalence class for single character
  196.  *
  197.  * synopsis
  198.  *    int tch, fwd[], bck[];
  199.  *    mkechar( tch, fwd, bck );
  200.  */
  201.  
  202. mkechar( tch, fwd, bck )
  203. int tch, fwd[], bck[];
  204.  
  205.     {
  206.     /* if until now the character has been a proper subset of
  207.      * an equivalence class, break it away to create a new ec
  208.      */
  209.  
  210.     if ( fwd[tch] != NIL )
  211.     bck[fwd[tch]] = bck[tch];
  212.  
  213.     if ( bck[tch] != NIL )
  214.     fwd[bck[tch]] = fwd[tch];
  215.  
  216.     fwd[tch] = NIL;
  217.     bck[tch] = NIL;
  218.     }
  219.